/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        int n = preorder.size();
        if (n == 1)
            return new TreeNode(preorder[0]);

        return dfs(preorder, 0, n - 1, inorder, 0, n - 1);
    }

    TreeNode* dfs(vector<int>& prev, int begin1, int end1, vector<int>& in, int begin2, int end2)
    {
        TreeNode* root = new TreeNode(prev[begin1]);

        if (begin1 == end1)
            return root;

        int mid = begin2;
        while (in[mid] != prev[begin1]) mid++;
        int lenth = mid - begin2;

        if (mid > begin2)
            root->left = dfs(prev, begin1 + 1, begin1 + lenth, in, begin2, mid - 1);
        if (mid < end2)
            root->right = dfs(prev, begin1 + lenth + 1, end1, in, mid + 1, end2);
        return root;
    }
};